package Hot100.Medium.String_2Pointer.String;

import java.util.Deque;
import java.util.LinkedList;

public class LC239_MaxValueOfSlidingWindow {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        //算法核心：deque中元素是从大到小的顺序存储滑动窗口的元素索引，队头永远是当前窗口最大值的索引下标
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < nums.length; i++)
        {
            //移除队列中不在滑动窗口范围内的元素
            if(!deque.isEmpty() && deque.peekFirst() < i - k + 1){
                deque.pollFirst();
            }
            //新元素进来时，把队列中比它小的都踢掉（因为它们永远不会成为最大值了）
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
                deque.pollLast();
            }
            //从队列的后面插入当前的数
            deque.offerLast(i);
            //当遍历到第k个元素时，开始记录窗口最大值
            if(i >= k - 1)
            {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}
